﻿#define  _CRT_SECURE_NO_WARNINGS

//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
//如果两个链表不存在相交节点，返回 null 。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* listA = headA;
    struct ListNode* listB = headB;
    int lenA = 0;
    int lenB = 0;
    while (listA->next) {
        listA = listA->next;
        lenA++;
    }
    while (listB->next) {
        listB = listB->next;
        lenB++;
    }
    if (listA != listB) {
        return NULL;
    }
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if (lenA < lenB) {
        longList = headB;
        shortList = headA;
    }
    int gap = abs(lenA - lenB);
    while (gap) {
        longList = longList->next;
        gap--;
    }
    while (longList) {
        if (longList == shortList) {
            return longList;
        }
        longList = longList->next;
        shortList = shortList->next;
    }
    return;

}
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
//
//不允许修改 链表。
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/linked-list-cycle-ii
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* meet = NULL;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            meet = fast;
            break;
        }
    }
    if (meet == head) {
        return head;
    }
    if (meet) {
        struct ListNode* meetnext = meet->next;
        meet->next = NULL;
        struct ListNode* listA = head;
        struct ListNode* listB = meetnext;
        int lenA = 0;
        int lenB = 0;
        while (listA) {
            listA = listA->next;
            lenA++;
        }
        while (listB) {
            listB = listB->next;
            lenB++;
        }
        int gap = abs(lenA - lenB);
        struct ListNode* longList = head;
        struct ListNode* shortList = meetnext;
        if (lenA < lenB) {
            struct ListNode* longList = meetnext;
            struct ListNode* shortList = head;
        }
        while (gap) {
            longList = longList->next;
            gap--;
        }
        while (longList) {
            if (longList == shortList) {
                return longList;
            }
            longList = longList->next;
            shortList = shortList->next;

        }

    }
    return NULL;
}